package com.dyz.leetcode;

public class Trap {
    //动态规划
    public int trap(int[] height) {
        if(height.length<=2){
            return 0;
        }
        int len = height.length;
        int [] maxArr = new int[len];//装满水的数组（左边递增，右边递减）
        //求出最大值的下标（如果存在多个最大值，则取得最左边的那个）
        int max = 0;
        int maxIndex = 0;
        for(int i=0; i<len; i++){
            if(height[i]>max){
                max = height[i];
                maxIndex = i;
            }
        }
        //初始化 特殊值
        maxArr[maxIndex] = max;
        maxArr[0] = height[0];
        maxArr[len-1] = height[len-1];
        //以最大值未分界线，左边递增，右边递减
        for(int i=1; i<maxIndex; i++){
            maxArr[i] = Math.max(maxArr[i-1], height[i]);
        }

        for(int i=len-2; i>maxIndex; i--){
            maxArr[i] = Math.max(height[i], maxArr[i+1]);
        }

        //计算
        int count = 0;
        for(int i = 0; i<len; i++){
            int temp = maxArr[i]-height[i];
            count = count +temp;
        }
        return count;
    }
}
